from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head:
            return
        stack = []
        p = head
        while p:
            stack.append(p)
            p = p.next
        i ,j = 0,len(stack)-1
        while i<j:
            stack[i].next  = stack[j]
            i+=1
            if i== j:
                break
            stack[j].next = stack[i]
            j-=1
        stack[i].next = None
# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    # your test code here